module fn.adt.tree.transform.Substitute

open System.Collections.Generic

open fn.adt.Tree


type TreeSubstitution<'D when 'D : equality> (replacements: IDictionary<'D, Tree<'D>>) =
    class
        let _replacements = replacements
        member this.apply (t: Tree<'D>) =
            let reapply (Node(r,sb)) = Node(r, [for s in sb -> this.apply s])
            match t with
            | Node(r, sb) as tx when (_replacements.ContainsKey(r)) ->
                match _replacements.Item(r) with
                | Node(r', []) -> reapply (Node(r', sb))
                | Node(r', sb') as rx when (sb = []) -> rx
                | _ -> reapply tx
            | tx -> reapply tx
    end


